package com.example.system.class19;

/**
 * @Date 2022/8/11
 * @Author Jonathan
 */
public class Code01_RobotWalk {
    public static void main(String[] args) {
        // 动态规划的效率居然比递归要低
        final long t1 = System.currentTimeMillis();
        for (int i = 0; i < 1; i++) {
            ways(20, 2, 4, 40);
        }
        final long t2 = System.currentTimeMillis();
        System.out.printf("递归时间:%d\n", (t2 - t1));
        for (int i = 0; i < 1; i++) {
            ways2(20, 2, 4, 40);
        }
        final long t3 = System.currentTimeMillis();
        System.out.printf("记忆化搜索时间:%d\n", (t3 - t2));
    }

    /**
     * @param N     一共有多少格子
     * @param start 起始位置
     * @param aim   终点位置
     * @param k     走多少步
     */
    public static int ways(int N, int start, int aim, int k) {
        return process(k, start, aim, N);
    }

    public static int process(int rest, int cur, int aim, int N) {
        // 没有剩余步数的情况下 就看当前所在的位置
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        // 在最左边 的时候只有一个方向
        if (cur == 1) {
            return process(rest - 1, 2, aim, N);
        }

        // 在最右边 的时候只有一个方向
        if (cur == N) {
            return process(rest - 1, N - 1, aim, N);
        }
        // 下一步往左或者往右
        return process(rest - 1, cur + 1, aim, N) + process(rest - 1, cur - 1, aim, N);
    }

    public static int ways2(int N, int start, int aim, int k) {
        int[][] dp = new int[N + 1][k + 1];
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < k + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(k, start, aim, N, dp);
    }

    // 记忆化搜索 ==> 动态规划
    public static int process2(int rest, int cur, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 没有剩余步数的情况下 就看当前所在的位置
        int ans;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
            dp[cur][rest] = ans;
            return ans;
        }
        // 在最左边 的时候只有一个方向
        if (cur == 1) {
            ans = process2(rest - 1, 2, aim, N, dp);
            dp[cur][rest] = ans;
            return ans;
        }

        // 在最右边 的时候只有一个方向
        if (cur == N) {
            ans = process2(rest - 1, N - 1, aim, N, dp);
            dp[cur][rest] = ans;
            return ans;
        }
        // 下一步往左或者往右
        ans = process2(rest - 1, cur + 1, aim, N, dp) + process2(rest - 1, cur - 1, aim, N, dp);
        dp[cur][rest] = ans;
        return ans;
    }

}
